package lib

//link to 5
func init() {
	Probs = append(Probs, Problem{
		Num:         516,
		Discription: "最长回文子序列",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
		},
	})
}

func LongestPalindromeSubseq(s string) int {
	n := len(s)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][i+1] = 1
	}

	for i := n - 1; i >= 0; i-- {
		for j := i + 2; j <= n; j++ {
			dp[i][j] = max(dp[i+1][j], dp[i][j-1])
			if s[i] == s[j-1] {
				dp[i][j] = max(dp[i][j], dp[i+1][j-1]+2)
			}
		}
	}

	return dp[0][n]
}
